common types of time complexity in big O Notation

Big O Notation 有幾個常見的值，越上面的值表示效率越好，反之則越差

1. O(1) Constant Time Complexity
   Constant time complexity,which always take same amount of time to be executed, no matter what value of input size is.
   不管 input size 為何，執行所耗費的時間都固定，效率最優
   E.g accessing value with an array index
2. O(log n) Logarithmic Time Complexity
   Logarithmic Time Complexity means that the running time of an algorithm is proportional to the logarithm of the input size.
   執行所耗費的時間與 input size 取對數成正比，效率良好
   E.g binary search algorithm 之後會介紹
3. O(n) Linear Time Complexity
   Linear time complexity means that running time of an algorithm grows linearly with the size of the input.
   執行所耗費的時間與 input size 成線性增長，效率一般
   E.g traverses through an array to find specific element (single loop) / 遍歷整個 array
4. O(n log n) **Logarithmic Time Complexity **
   E.g sorting algorithm 之後會介紹
5. O(n^2) / O(n^3) Quadratic Time Complexity
   E.g nested iteration (nested loops)
   執行所耗費的時間與 input size 成次方增長，效率差
6. O(2^n) Exponential Time Complexity
   執行所耗費的時間與 input size 成指數增長，效率差(比n^2更差一些)
7. O(n!)執行所耗費的時間與 input size 成階層增長，效率極差

附上不同value of Big O 於 desmos 的做圖
可看出當 input size 增長，不同 big O 的 function complexity 的趨勢如何增長

下圖說明了不同Big O的複雜性與優劣

圖片來源

相關資源

Beginners Guide to Big O Notation
https://www.freecodecamp.org/news/my-first-foray-into-technology-c5b6e83fe8f1/
Common Big-O Notations
https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/#common-bigo-notations
Big O Cheat Sheet – Time Complexity Chart
https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/